【真题 + 解析】2022 CSP

2022 CCF非专业级别软件能力认证第一轮

（CSP-J1）入门级 C++语言试题

认证时间：2022年 9月 18日 09:30~11:30

考生注意事项：

 试题纸共有 12页，答题纸共有 1页，满分 100分。请在答题纸上作答，写在试题纸上的

一律无效。

 不得使用任何电子设备（如计算器、手机、电子词典等）或查阅任何书籍资料。

1. 以下哪种功能没有涉及 C++语言的面向对象特性支持：（）。

A. C++中调用 printf函数（printf 为C语言的输出语句）

B. C++中调用用户定义的类成员函数

C. C++中构造一个 class或 struct

D. C++中构造来源于同一基类的多个派生类

2. 有 6个元素，按照 6、5、4、3、2、1的顺序进入栈 S，请问下列哪个出栈序列是非法的

（ ）。

A. 5 4 3 6 1 2

B. 4 5 3 1 2 6

C. 3 4 6 5 2 1 ： 进栈：6 5 4 3；出栈 3 4；错误5没有出栈，6不能出栈

D. 2 3 4 1 5 6

3. 运行以下代码片段的行为是（ ）。

int x = 101;

int y = 201;

int *p = &x;

int *q   = &y;

p = q;

A. 将 x的值赋为 201

B. 将 y的值赋为 101

C. 将 q指向 x的地址

D. 将 p指向 y的地址：p和q都存储了y的地址，都指向y

4. 链表和数组的区别包括（ ）。

A. 数组不能排序，链表可以

B. 链表比数组能存储更多的信息

C. 数组大小固定，链表大小可动态调整：链表和数组都能排序，都能存储很多数据

D. 以上均正确

5. 对假设栈 S和队列 Q的初始状态为空。存在 e1~e6六个互不相同的数据，每个数据按照

进栈 S、出栈 S、进队列 Q、出队列 Q的顺序操作，不同数据间的操作可能会交错。已知

栈 S中依次有数据 e1、e2、e3、e4、e5和 e6进栈，队列 Q依次有数据 e2、e4、e3、

e6、e5和 e1出队列。则栈 S的容量至少是（ ）个数据。

A. 2

B. 3：模拟一下：e1进栈(1)、e2进栈(2)、e2出栈(1)、e3进栈(2)、e4进栈(3)、e4出栈(2)、e3出栈(1)、e5进栈(2)、e6进栈(3)、e6出栈(2)、e5出栈(1)、e1出栈(0)，因此栈S的容量至少为3

C. 4

D. 6

6. 对表达式 a+(b-c)*d的前缀表达式为（ ），其中+、-、*是运算符。

A. *+a-bcd

B. +a*-bcd：加括号法：(a+( (b-c)*d) )  -bc;  *-bcd;  +a*-bcd

C. abc-d*+

D. abc-+d

7. 假设字母表 {a, b, c, d, e} 在字符串出现的频率分别为 10%, 15%, 30%, 16%,

29%。若使用哈夫曼编码方式对字母进行不定长的二进制编码，字母 d的编码长度为

（ ）位。

A. 1

B. 2 ：按"哈夫曼编码"规则模拟,每次都选两个最小的合并,最后构建了一颗二叉树(哈夫曼树、最优二叉树),节点到根的边数就是编码位数

C. 2或 3

D. 3

8. 一棵有 n个结点的完全二叉树用数组进行存储与表示，已知根结点存储在数组的第 1个位

置。若存储在数组第 9个位置的结点存在兄弟结点和两个子结点，则它的兄弟结点和右子

结点的位置分别是（ ）。

A. 8、18

B. 10、18

C. 8、19：9 的父节点是4,兄弟是8,右儿子是19

D. 10、19

9. 考虑由 N个顶点构成的有向连通图，采用邻接矩阵的数据结构表示时，该矩阵中至少存在

（ ）个非零元素。

A. N-1

B. N 考察选手对连通图的理解，连通图需要保证所有节点被链接，无向连通图n个节点至少需要n-1条边，因为题目说的是有向图，无反向边，所以邻接矩阵中至少有n个节点不是0。n个点有向连通图，至少有n条边，连成一圈，邻接矩阵中非零元素即为边数最少为n。

C. N+1

D. N2

10.以下对数据结构的表述不恰当的一项为：（ ）。

A. 图的深度优先遍历算法常使用的数据结构为栈。

B. 栈的访问原则为后进先出，队列的访问原则是先进先出。

C. 队列常常被用于广度优先搜索算法。

D. 栈与队列存在本质不同，无法用栈实现队列。：两个栈就可以模拟队列了

11.以下哪组操作能完成在双向循环链表结点 p之后插入结点 s的效果（其中，next域为结

点的直接后继，prev域为结点的直接前驱）：（ ）。

A. p->next->prev=s; s->prev=p; p->next=s; s->next=p->next;

B. p->next->prev=s; p->next=s; s->prev=p; s->next=p->next;

C. s->prev=p; s->next=p->next; p->next=s; p->next->prev=s;

D. s->next=p->next; p->next->prev=s; s->prev=p; p->next=s;

画图模拟就行

12.以下排序算法的常见实现中，哪个选项的说法是错误的：（ ）。

A. 冒泡排序算法是稳定的

B. 简单选择排序是稳定的：常见排序中，稳定排序有冒泡排序、插入排序、归并排序、堆排序，不稳定排序有：快速排序、选择排序

C. 简单插入排序是稳定的

D. 归并排序算法是稳定的

13.八进制数 32.1对应的十进制数是（ ）。

A. 24.125

B. 24.250

C. 26.125  按权展开，3×8 + 2×1 + 1×1/8 = 26.125

D. 26.250

14.一个字符串中任意个连续的字符组成的子序列称为该字符串的子串，则字符串 abcab有

（ ）个内容互不相同的子串。

A. 12

B. 13：手动模拟各个长度下的子串数量,注意空串 和自己也是子串。子串有：空串a ab abe abca abcab b be bca bcab c ca   cab 共12个

C. 14

D. 15

15.以下对递归方法的描述中，正确的是：（ ）

A. 递归是允许使用多组参数调用函数的编程技术

B. 递归是通过调用自身来求解问题的编程技术：递归参数数量随意;调用自身;面向功能和 逻辑;不是编译;

C. 递归是面向对象和数据而不是功能和逻辑的编程语言模型

D. 递归是将用某种高级语言转换为机器代码的编程技术

(1)

假设输入的 x、y均是不超过 15的自然数，完成下面的判断题和单选题：

 判断题

16. 删去第 7行与第 13行的 unsigned，程序行为不变。（对）unsigned删除相当于少一位,最大的数字是 0x55=01010101B,不需要最高位。

17. 将第 7行与第 13行的 short均改为 char，程序行为不变。（错）输入2位数就错了,字符只能存一位

18. 程序总是输出一个整数“0”。（错 ）输入2 2结果12

19. 当输入为“2 2”时，输出为“10”。 （错 ）

20. 当输入为“2 2”时，输出为“59”。 （错 ）

 单选题

位运算模拟自己代入计算：先计算